# -*- coding: utf-8 -*-

'''
@author: Luis Fonte n6043
@date: 10/06/2013
@obs: Code created on class from documentation given by teacher
'''

from random import uniform
from time import clock


class Quick():
    '''
    Class Quick
    Class with a quick sort algorithm implemented on function quicksort
    '''
    
    def __init__(self, A):
        '''
        Class constructor
        @param A - list with numbers desordered
        '''
        self.A = A  #list desordered
        self.p = 0
        self.r = len(self.A)-1
        pass

    
    def partition(self, A, p, r):
        '''
        function partition
        Divides list in two partitions 
        @param A - list with numbers
        @param p - index of A (first value)
        @param r - index of A (last value-1)
        '''
        x = A[r]
        i = p - 1
        for j in range(p, r):
            if A[j] <= x:
                i = i + 1
                A[i], A[j] = A[j], A[i]
                pass
            pass  
        A[i+1], A[r] = A[r], A[i+1]   
        return i+1

    def quicksort(self, A, p, r):
        '''
        function quicksort
        Orders the two tables partitioned
        @param A - list with numbers
        @param p - index of A (first value)
        @param r - index of A (last value-1)
        '''
        if p < r:
            q = self.partition(A,p,r)
            self.quicksort(A,p,q-1)
            self.quicksort(A,q+1,r)
            pass
        pass
    
    def quick(self):
        '''
        function quicks
        Calls function quickSort passing parameters
        this function is used to simplify user's dificulty using this library
        All is need is passing the list by parameter on class object creation
        '''
        self.quicksort(self.A, self.p, self.r)
        pass

